package cn.z2huo.algorithm.sort.insert.half;

import java.util.Arrays;

/**
 * <p>折半插入排序，用折半查找来寻找待插入元素在已排序序列中应该插入的位置。
 *
 * <p>减少了关键字之间的比较次数，但是记录的移动次数不发生变化。时间复杂度仍为O(n^2)
 *
 * 算法困惑点在于：为什么最后找到元素插入位置之后，插入元素的位置要以low来确定，为什么不是middle
 *
 * @author z2huo
 */
public class HalfInsertSorting {

    public int[] sort(int[] array) {
        if (array == null || array.length == 0) {
            return new int[0];
        }



        // 此循环每一次遍历前，索引位置小于 i 的子序列都是正序的
        // 循环遍历是为了寻找 i 位置的元素在有序子序列中正确的位置
        for (int i = 1; i < array.length; i++) {
            int element = array[i];
            int j = i - 1;
            // 当 i 位置的元素小于 j 位置的元素时
            // 将 j 位置的元素向右移动一位
            // 之后 j 会递减，也就是继续判断再左一位的元素与 i 位置元素的大小，满足条件时继续向右移动
            // 直到 j < 0 或者 j 位置的元素大于 i 位置的元素时，跳出循环
            for (; j >= 0 && element < array[j]; j--) {
                array[j + 1] = array[j];
            }
            // 跳出循环前会执行 j--，所以 i 位置元素最终所处的位置为 j + 1
            array[j + 1] = element;
        }
        return array;
    }

    public int[] sort2(int[] array) {
        if (array == null) {
            return null;
        }
//        2 3 4 3
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int low = 0, high = i - 1;
            int middle = 0;
            // 折半查找，为了寻找 array[i] 在已排序序列中应该插入的位置，
            // 如果已排序序列中不存在array[i]该插入的位置，则插入位置还为原位置i，由low来决定的
            while (low <= high) {
                middle = (high + low) / 2;
                if (temp > array[middle]) {
                    low = middle + 1;
                } else {
                    high = middle - 1;
                }
            }
//            跟下面的for循环结果相同，但是low和middle却不同，middle会比low小1
//            当low为下界时，该循环跳过，当middle为下界时，循环执行一次，i处覆盖掉的值会被array[low]重新赋值
//            for (int j = i - 1; j >= low; j--) {
//                array[j + 1] = array[j];
//            }
//            array[low] = temp;
            for(int j = i-1; j>= middle; j--){
                array[j+1] = array[j];
            }
            array[low] = temp;
        }
        System.out.println(Arrays.toString(array));
        return array;
    }
}
